﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

//单链表OJ题(牛哥+力扣）

//1. 删除链表中等于给定值 val 的所有节点。
/*Definition for singly-linked list.*/
struct ListNode 
{
     int val;
     struct ListNode *next;
};
 
//写法一
struct ListNode* removeElements1(struct ListNode* head, int val)
{
    struct ListNode* cur = head;
    struct ListNode* Prev = NULL;
    while (cur != NULL)
    {
        //移除
        if (cur->val == val)
        {
            //头删
            if (Prev == NULL)
            {
                head = head->next;
                free(cur);
                cur = head;
            }
            //非头删
            else
            {
                Prev->next = cur->next;
                free(cur);
                cur = Prev->next;
            }
        }
        //跳过
        else
        {
            Prev = cur;
            cur = cur->next;
        }
    }

    return head;
}

//写法二
struct ListNode* removeElements2(struct ListNode* head, int val)
{
    struct ListNode* cur = head;
    struct ListNode* tail = NULL;
    head = NULL;//！
    while (cur != NULL)
    {
        //删除
        if (cur->val == val)
        {
            struct ListNode* del = cur;
            cur = cur->next;
            free(del);
        }
        //不是valu的节点，拿下来尾插到新的单链表
        else
        {
            //第一次插入
            if (tail == NULL)
            {
                tail = cur;
                head = cur;
            }
            else
            {
                tail->next = cur;
                tail = tail->next;
            }
            cur = cur->next;
        }
    }
    if (tail != NULL)//！
    {
        tail->next = NULL;
    }

    return head;
}

//写法三
struct ListNode* removeElements3(struct ListNode* head, int val)
{
    struct ListNode* cur = head;
    struct ListNode* tail = NULL;
    //带有哨兵位的
    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    assert(tail);

    while (cur != NULL)
    {
        //删除
        if (cur->val == val)
        {
            struct ListNode* del = cur;
            cur = cur->next;
            free(del);
        }
        //不是valu的节点，拿下来尾插到新的单链表
        else
        {
            tail->next = cur;
            tail = tail->next;
            cur = cur->next;
        }
    }
    tail->next = NULL;
    //释放空间
    struct ListNode* del = head;
    head = head->next;
    free(del);

    return head;
}

//int main()
//{
//    int a = 5;
//    int b, c = 0;
//    b = c = a;      //可以连续赋值
//    printf("%d %d", b, c);
//
//    return 0;
//}


//2. 反转一个单链表。
//方法一
struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* newhead = NULL;
    struct ListNode* cur = head;
    struct ListNode* nextone = NULL;

    //依次头插就反转了
    while (cur != NULL)
    {
        nextone = cur->next;

        cur->next = newhead;
        newhead = cur;
        cur = nextone;
    }

    return newhead;
}
//方法二
struct ListNode* reverseList(struct ListNode* head)
{
    if (head == NULL)
    {
        return NULL;
    }
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    struct ListNode* nextone = cur->next;

    //颠倒指针
    while (cur != NULL)
    {
        cur->next = prev;
        prev = cur;
        cur = nextone;
        if (nextone != NULL)
        {
            nextone = nextone->next;
        }
    }

    return  prev;
}

//给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个
//中间结点。

//方法：快慢指针
struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* slow = NULL;
    struct ListNode* fast = NULL;
    fast = slow = head;

    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

//输入一个链表，输出该链表中倒数第k个结点
//方法一 fast先走k-1步
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{
    struct ListNode* slow = NULL;
    struct ListNode* fast = NULL;
    slow = fast = pListHead;

    //fast先走k-1步
    while (--k)
    {
        //k-1步还没有走完，链表没有k-1步长
        if (fast == NULL)
        {
            return NULL;
        }
        fast = fast->next;
    }
    //由于是--k，还可能出现一种情况：当k==1时，fast已经为空
    //但此时无法进入循环，也就无法return
    //eg：1,{1,2,3,4,5}
    //让fast先走k步会简单一些
    if (fast != NULL)
    {
        while (fast->next != NULL)
        {
            //slow、fast一起走
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }

    return NULL;
}

//方法二 fast先走k步
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{
    struct ListNode* slow = NULL;
    struct ListNode* fast = NULL;
    slow = fast = pListHead;

    //fast先走k步
    while (k--)
    {
        //k步还没有走完，fast就为空了
        //链表长度小于k
        if (fast == NULL)
        {
            return NULL;
        }
        fast = fast->next;
    }
    //一起走
    while (fast != NULL)
    {
        slow = slow->next;
        fast = fast->next;
    }

    return slow;
}

// 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
//方法一
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode* head = NULL;
    struct ListNode* tail = NULL;
    if (list1 == NULL)
    {
        return list2;
    }
    if (list2 == NULL)
    {
        return list1;
    }

    while (list1 != NULL && list2 != NULL)
    {
        if (list1->val < list2->val)
        {
            if (tail == NULL)
            {
                head = tail = list1;
            }
            else
            {
                tail->next = list1;
                tail = tail->next;
            }
            list1 = list1->next;
        }
        else
        {
            if (tail == NULL)
            {
                head = tail = list2;
            }
            else
            {
                tail->next = list2;
                tail = tail->next;
            }
            list2 = list2->next;
        }
    }
    if (list2 == NULL)
    {
        tail->next = list1;
    }
    if (list1 == NULL)
    {
        tail->next = list2;
    }

    return head;
}

//方法二（哨兵位）
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode* head = NULL;
    struct ListNode* tail = NULL;
    //带哨兵位的链表
    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    tail->next = NULL;

    while (list1 != NULL && list2 != NULL)
    {
        if (list1->val < list2->val)
        {

            tail->next = list1;
            tail = tail->next;
            list1 = list1->next;
        }
        else
        {
            tail->next = list2;
            tail = tail->next;
            list2 = list2->next;
        }
    }

    if (list2 == NULL)
    {
        tail->next = list1;
    }
    if (list1 == NULL)
    {
        tail->next = list2;
    }
    struct ListNode* nextone = head->next;
    free(head);

    return nextone;
}

// 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
struct ListNode* partition(struct ListNode* pHead, int x)
{
    struct ListNode* lesshead, * lesstail, * greaterhead, * greatertail;
    //定义两个哨兵位
    lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
    greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode));
    lesstail->next = NULL;
    greatertail->next = NULL;
    struct ListNode* cur = pHead;

    while (cur)
    {
        if (cur->val < x)
        {
            lesstail->next = cur;
            lesstail = lesstail->next;
        }
        else
        {
            greatertail->next = cur;
            greatertail = greatertail->next;
        }

        cur = cur->next;
    }

    //合并到一起
    lesstail->next = greaterhead->next;
    greatertail->next = NULL;

    //释放malloc
    struct ListNode* nextone = lesshead->next;
    free(lesshead);
    free(greaterhead);

    return nextone;
}

// 链表的回文结构。回文->对称
//需要调用之前写的函数
//使用bool类型，需要引用 #include <stdbool.h>
bool chkPalindrome(struct ListNode* A)
{
    struct ListNode* head = A;
    //找中间节点
    struct ListNode* mid = middleNode(head);
    //从中间节点开始逆置
    struct ListNode* rhead = reverseList(mid);

    while (head != NULL && rhead != NULL)
    {
        if (head->val != rhead->val)
        {
            return false;
        }
        head = head->next;
        rhead = rhead->next;
    }

    return true;
}
//输入两个链表，找出它们的第一个公共结点。
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
    //一定没有交点
    if (headA == NULL || headB == NULL)
    {
        return NULL;
    }

    struct ListNode* curA, * curB = NULL;
    curA = headA;
    curB = headB;

    //求出链表的长度
    int lenA = 1;
    int lenB = 1;
    while (curA->next != NULL)
    {
        curA = curA->next;
        lenA++;
    }
    while (curB->next != NULL)
    {
        curB = curB->next;
        lenB++;
    }
    //判断链表是否相交
    if (curA != curB)
    {
        return NULL;
    }
    //链表相交，找交点
    //假设A短，B长
    struct ListNode* shorList = headA;
    struct ListNode* longList = headB;
    //假设失败，修正
    if (lenA > lenB)
    {
        shorList = headB;
        longList = headA;
    }
    //求长度的差值
    int gap = abs(lenA - lenB);
    //长的先走差值步
    while (gap--)
    {
        longList = longList->next;
    }
    //一起走
    while (shorList != longList)
    {
        shorList = shorList->next;
        longList = longList->next;
    }

    return shorList;
}
//给定一个链表，判断链表中是否有环。
bool hasCycle(struct ListNode* head)
{
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
        //进入环后，fast超过slow
        if (slow == fast)
        {
            return true;
        }
    }
    //没有环
    return false;
}
//给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
struct ListNode* detectCycle(struct ListNode* head)
{
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    struct ListNode* cur = head;
    //先判断是否有环
    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            //记录相遇点
            struct ListNode* meet = slow;
            while (cur != meet)
            {
                cur = cur->next;
                meet = meet->next;
            }
            printf("%d", cur->val);
            return cur;
        }
    }

    //没有环
    return NULL;
}

// 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点，要求返回这个链表的深度拷贝
struct Node
{
    int val;
    struct Node* next;
    struct Node* random;
};

struct Node* copyRandomList(struct Node* head)
{
    //1.把copy的节点一次插入到原节点的后后面
    struct Node* cur = head;

    while (cur != NULL)
    {
        struct Node* nextone = cur->next;
        //开辟copy的节点
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        if (copy == NULL)
        {
            perror("malloc");
            exit(-1);
        }
        copy->val = cur->val;
        //插入
        cur->next = copy;
        copy->next = nextone;
        cur = nextone;
    }
    //2.搞定copy的random
    cur = head;
    while (cur != NULL)
    {
        struct Node* copy = cur->next;
        if (cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }

        cur = copy->next;
    }
    //3.copy的节点接下来，尾插到新链表，并恢复原链表
    cur = head;
    struct Node* copyhead = NULL;
    struct Node* copytail = NULL;

    while (cur != NULL)
    {
        struct Node* copy = cur->next;
        struct Node* nextone = copy->next;
        //尾插(第一个)
        if (copytail == NULL)
        {
            copyhead = copytail = copy;
        }
        //(正常)
        else
        {
            copytail->next = copy;
            copytail = copytail->next;
        }

        cur->next = nextone;
        cur = nextone;
    }

    return copyhead;
}